/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   vector_impl.h                                      :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: Jiang <767280080@qq.com>                   +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2024/04/23 12:29:12 by Jiang             #+#    #+#             */
/*   Updated: 2024/04/24 09:59:20 by TYTY000          ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#ifndef __vector_impl__
#define __vector_impl__

template <typename T> void Vector<T>::copyFrom(const T *A, Rank lo, Rank hi) {
  _elem = new T[_capacity = 2 * (hi - lo)];
  _size = 0;
  while (hi > lo)
    _elem[_size++] = A[lo++];
}

template <typename T> T &Vector<T>::operator[](Rank r) { return _elem[r]; }

template <typename T> const T &Vector<T>::operator[](Rank r) const {
  return _elem[r];
}

template <typename T> Vector<T> &Vector<T>::operator=(const Vector<T> &v) {
  if (this != &v) {
    if (_elem)
      delete[] _elem;
    copyFrom(v._elem, 0, v.size());
  }
  return *this;
}

template <typename T> void Vector<T>::expand() {
  if (_size < _capacity)
    return;
  if (_capacity < DEFAULT_CAPA)
    _capacity = DEFAULT_CAPA;
  T *ptr = _elem;
  _elem = new T[_capacity <<= 1];
  for (Rank i = 0; i < _size; i++)
    _elem[i] = ptr[i];
  delete[] ptr;
}

template <typename T> void Vector<T>::shrink() {
  if (_capacity < DEFAULT_CAPA << 1)
    return;
  if (_size << 2 > _capacity)
    return;
  T *ptr = _elem;
  _elem = new T[_capacity >>= 1];
  for (Rank i = 0; i < _size; i++)
    _elem[i] = ptr[i];
  delete[] ptr;
}

template <typename T> Rank Vector<T>::maxItem(Rank lo, Rank hi) {
  Rank r = hi;
  while (lo < hi--)
    if (_elem[hi] > _elem[r])
      r = hi;
  return r;
}

template <typename T> Rank Vector<T>::find(const T &e, Rank lo, Rank hi) const {
  while ((lo < hi--) && (_elem[hi] != e))
    ;
  return hi;
}

#include "../fib/fib.h"

template <typename T>
static Rank fibSearch(T *A, const T &e, Rank lo, Rank hi) {
  Fib fib(hi - lo);
  while (hi > lo) {
    while (hi - lo < fib.get())
      fib.prev();
    Rank mi = lo + fib.get() - 1;
    if (e < A[mi])
      hi = mi;
    else
      lo = mi + 1;
  }
  return lo - 1;
}

template <typename T>
Rank Vector<T>::search(const T &e, Rank lo, Rank hi) const {
  return fibSearch(_elem, e, lo, hi);
}

template <typename T> void Vector<T>::sort(Rank lo, Rank hi) {
  switch (rand() % 3) {
  case 1:
    bubbleSort(lo, hi);
    break;
  case 2:
    selectionSort(lo, hi);
    break;
  default:
    mergeSort(lo, hi);
    break;
  }
}

template <typename T> void Vector<T>::unsort(Rank lo, Rank hi) {
  T *S = _elem + lo;
  for (Rank i = hi - lo; i > 0; i--)
    std::swap(S[i - 1], S[rand() % i]);
}

template <typename T> Rank Vector<T>::insert(Rank r, const T &e) {
  expand();
  for (Rank i = _size; i > r; i--)
    _elem[i] = _elem[i - 1];
  _elem[r] = e;
  _size++;
  return r;
}

template <typename T> Rank Vector<T>::remove(Rank lo, Rank hi) {
  if (lo == hi)
    return 0;
  while (hi < _size)
    _elem[lo++] = _elem[hi++];
  _size -= (hi - lo);
  shrink();
  return hi - lo;
}

template <typename T> T Vector<T>::remove(Rank r) {
  T old = _elem[r];
  remove(r, r + 1);
  return old;
}

template <typename T> Rank Vector<T>::deduplicate() {
  Rank oldSize = _size;
  Rank i = 1;
#ifdef vector_debug
  std::cout << "remove : ";
#endif
  while (i < _size)
    if (find(_elem[i], 0, i) == -1)
      i++;
    else
#ifdef vector_debug
      std::cout << remove(i) << '\t';
#endif
#ifndef vector_debug
  remove(i);
#endif
  std::cout << '\n';
  return oldSize - _size;
}

template <typename T> Rank Vector<T>::uniquify() {
  Rank i = 0, j = 0;
  std::cout << "remove : ";
  while (++j < _size)
    if (_elem[i] != _elem[j])
      _elem[++i] = _elem[j];
    else
      std::cout << _elem[i] << '\t';
  _size = ++i;
  shrink();
  std::cout << '\n';
  return j - i;
}

template <typename T> Rank Vector<T>::disordered() {
  int cnt = 0;
  for (Rank i = 1; i < _size; i++)
    if (_elem[i - 1] > _elem[i])
      cnt++;
  return cnt;
}

template <typename T> void Vector<T>::traverse(void (*visit)(T &)) {
  for (auto &it : *this) {
    visit(it);
  }
  // for (Rank i = 0; i < _size; i++) {
  //   visit(_elem[i]);
  // }
}

template <typename T>
template <typename VST>
void Vector<T>::traverse(VST &visit) {
  for (auto it : *this) {
    visit(it);
  }
  // for (Rank i = 0; i < _size; i++) {
  //   visit(_elem[i]);
  // }
}

#include "vector_sort.h"
#endif // !__vector_impl__
